The present invention is directed to methods and devices for solving formulas having the form AB mod M, where A, B, and M are generally large numbers of the order 2N, N having a typical value of 1024. These modular exponential formulas are frequently used in RSA security modules for Internet protocols. To increase the speed of calculation of modular exponential formulas, several approaches have been developed, for example, the Montgomery algorithm. Other algorithms are described in Handbook of Applied Cryptography, A. J. Mezenes, P. C. van Oorschot, and S. A. Vanstone, CRC Press, 1996, pp. 591–634.
The Montgomery algorithm is a modular multiplication algorithm in which one reduction is performed at each iteration of the multiplication. An advantage of the Montgomery algorithm is that the modular reduction is performed by a shift instead of a division. However, further speed increases for modular exponentiation are desirable for more efficient secure communications.